//
//  Problem938.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/22.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 938
 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和

 示例 1：
                10
              /    \
             5     15
            / \      \
           3   7      18
 输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
 输出：32
 
 示例 2：
     输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
     输出：23

 提示：
     树中节点数目在范围 [1, 2 * 104] 内
     1 <= Node.val <= 105
     1 <= low <= high <= 105
     所有 Node.val 互不相同
 */
@objcMembers class Problem938: NSObject {
    func solution() {
        let root = TreeNode(10)
        root.left = TreeNode(5)
        root.left?.left = TreeNode(3)
        root.left?.right = TreeNode(7)
        
        root.right = TreeNode(15)
        root.right?.right = TreeNode(18)
        
        print(rangeSumBSTG(root, 7, 15))
    }
    
    /*
     递归：
     二叉搜索树：左 < 根 < 右
     判断当前的节点与 low和hight 的关系
     1: node.value > hight => 根 + 右侧 全都不满足， 递归左侧
     2: node.value < low   => 根 + 左侧 全都不满足， 递归右侧
     3: 其他：node.value + 递归(左) + 递归(右)
     */
    func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
        if root == nil {
            return 0
        }
        if root!.val > high {
            return rangeSumBST(root?.left, low, high)
        } else if root!.val < low {
            return rangeSumBST(root?.right, low, high)
        } else {
            return root!.val + rangeSumBST(root?.left, low, high) + rangeSumBST(root?.right, low, high)
        }
    }
    /*
     广度
     1: 创建一个数组，初始化时存储root
     2: 循环判断数组是否为空，依次从数组拿出一个值，然后判断node.value和row、hight的比较
     3: 和上面判断一下，把相应的放入数组尾部
     */
    func rangeSumBSTG(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
        if root == nil {
            return 0
        }
        var sum = 0
        var list:[TreeNode?] = [root]
        while list.isEmpty == false {
            guard let node = list.removeFirst() else {
                continue
            }
            
            if node.val > high {
                list.append(node.left)
            } else if node.val < low {
                list.append(node.right)
            } else {
                sum += node.val
                list.append(node.left)
                list.append(node.right)
            }
        }
        
        return sum
    }
    
}
